1. Field of the Invention
The present invention generally relates to authentication of data such as an image or video which survive incidental modifications to the data content caused by, for example, noise, lossy compression-decompression, or digital-to-analog-to-digital (D/A/D) conversion of the data file, which do not affect the authenticity of the file.
2. Description of the Related Art
In a world where electronic multimedia data such as images and video data are transferred and modified routinely, authentication of data becomes important in verifying the integrity of the data. In these applications, data being authentic includes the notions that the data has not been tampered with, or that it came from the right owner (i.e., the origin of the data can be verified). One of the requirements in an authentication system for multimedia data such as images, video and sound is that the data survives incidental modifications such as lossy compression-decompression, noise, printing and scanning, or digital-to-analog-to-digital conversion while retaining its authenticity. On the other hand, malicious modifications should render the data inauthentic. Such authentication systems are called robust authentication systems.
Almost all authentication systems proposed have the following general form. That is, some essential data is extracted from the source data, from which an authentication tag is created. The authentication tag is appended or inserted into the source data. The result is called authenticatable data. As the authentication tag is generally much smaller than the source, as some data reduction occurs in generating the tag. In some robust authentication systems, to enable authentication, the authenticatable data is distorted from the source data. This distortion is referred to as authenticatibility distortion.
To authenticate the authenticatable data, the appended (or inserted) authentication tag is extracted from the data. Next, the essential data is extracted from the data from which a second authentication tag is created. These two authentication tags are then compared. If they compare favorably, then the image is deemed authentic.
Most of the conventional robust authentication schemes can be classified into two classes. The main difference between the two classes lies in the way data reduction is performed.
The first class performs data reduction by extracting some relevant features (such as the edges in the image) from the data and uses them in the authentication tag (e.g., see “Content-based integrity protection of digital images”, Maria Paula Queluz, Proceedings of SPIE, vol. 3657, 85-93, 1999; “Compression Tolerant Image Authentication”, Sushil Bhattacharjee and Martin Kutter, Proc. ICIP 1998; and commonly-assigned U.S. patent application Ser. No. 09/398,203 entitled “Semi-fragile Watermarks” filed on Sep. 17, 1999 to Martens et al.).
In these systems, small changes in the image result in small changes in the tag. Furthermore, as authenticity is based on similarity between the two tags, small differences between the two tags do not destroy the authenticity of the file. There is little or no authenticability distortion.
However, a drawback of this type of authentication scheme is that, because small changes in the image result in small changes in the tag, it is potentially easy to find forged images which generate the same or similar tags as the original image. For example, as pointed out in “Distortion Bounded Authentication Techniques”, Nasir Memon, Poorvi Vora, Boon-Lock Yeo and Minerva Yeung, Proceedings of the SPIE, vol. 3971, pg. 164-174, 2000, many images have the same set of edges, yet the content of the images are different (e.g., an image of a coffee stain versus a blood stain). In the language of cryptography, the function which computes the tag from the original image is not pre-image resistant.
A second type of authentication scheme utilizes a cryptographic hash function to reduce the data and generate a relatively small tag from the image. In this case, the two tags must be identical to ensure authenticity. The reader is referred to, for example, the aforementioned paper by Memon et al. It is noted that cryptographic hashes have the property that small changes in the image result in large changes in the tag and the use of a cryptographic hash function makes it extremely difficult to generate forged images that have the same tag as the original image.
However, these methods modify the source image significantly in order for the image to be authenticatable (i.e., there is a significant amount of authenticability distortion). For example, in the paper by Memon et al., the pixels of the image are quantized and the quantized image is made authenticatable. The amount of authenticability distortion applied to the image can be as large as the maximum amount of modification to the image that the authentication system is willing to tolerate before the image is deemed inauthentic. This is not acceptable in cases where the authenticatable images must be of high quality, whereas images of a lesser quality can be considered authentic. This is especially true when the images are printed on paper and authentication is done by scanning the printed image. In an application such as the “digital notary” which will be presented below, the authentication distortion must be zero.